package com.johann.classify;

import com.johann.test.SwapArray;

/*
* 稳定的排序算法
* 时间复杂度（平均、最坏）：O(n^2)
* 时间复杂度（最好）：O(n)
* 空间复杂度：O(1)
* */
@SuppressWarnings("all")
public class BubbleSort {
    public <T extends Comparable> void bubbleSort(T [] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length-1- i; j++) {
                if(arr[j].compareTo(arr[j+1])>0){
                    T temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

    }
    //优化比较次数，如果上一次没有交换数字，直接退出
    public void bubbleSort02(Integer[] arr){
        boolean flag =true;
        for (int i = 0; i < arr.length - 1; i++) {
            if (!flag) {
                break;
            }
            flag = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j]>arr[j+1]) {
                    new SwapArray(arr, j, j + 1);
                    flag = true;
                }
            }
        }
    }


}
